When devising an Artificial Intelligence, a decision making process must be
defined. Several decision making algorithms exist, depending on different
structures. In favor of elegancy and simplicity, we chose to use a Decision Tree
model in this AI. Advantages of a decision tree are that it is easy to keep
track of why an artificial agent does what he does and that they are very simple
to construct, since they are functionally the same as if-then-else statements.

\subsection{Kill-First-AI}

\tikzset{
    every node/.style={
        font=\scriptsize
    },
    decision/.style={
        shape=rectangle,
        minimum height=1cm,
        text width=2cm,
        text centered,
        rounded corners=1ex,
        draw,
        label={[yshift=0.125cm]left:yes},
        label={[yshift=0.125cm]right:no},
    },
    outcome/.style={
        shape=ellipse,
        fill=gray!15,
        draw,
        text width=1.5cm,
        text centered
    },
    decision tree/.style={
        edge from parent path={[-latex] (\tikzparentnode) -| (\tikzchildnode)},
        %sibling distance=5cm,
        level distance=2cm
    }
}
\tikzset{level 1/.style={sibling distance=6cm}}
\tikzset{level 2/.style={sibling distance=3cm}}

\begin{figure}
\centering
%\includegraphics[width=10cm]{resources/tree1}
\begin{tikzpicture}[node distance =0cm, auto]
\node [decision] {Is current position safe?}
    [decision tree]
    child { node [decision] { Is there a reachable enemy? } 
        child { node [outcome] { attack enemy } }
        child { node [decision] { Is there a reachable power up? } 
            child { node [outcome] { Go to power up } }
            child { node [outcome] { Clear path to enemy } }
        }
    }
    child { node [decision] { Is there a safe position nearby?}
            child { node [outcome] { Go to safe position} }
            child { node [outcome] { Do nothing} }
    };
\end{tikzpicture}
\caption{Decision Tree for the Kill-First AI}
\label{fig:tree1}
\end{figure}

The Kill-First-AI is a version that prioritizes killing the enemy over anything
else. Its decision tree can be seen in figure \ref{fig:tree1}. As you can see
the logic behind the AI agents is relatively simple, in a step by step
breakdown of the figure above we see the states of the agent being divided
into two different categories. One is the case in which the current position
of the agent is safe and the agent has time to plot its next move and the
other is when the agents position is threatened by a bomb. This is the major
concern of the agent when checking for the next move. 

In case the current position is threatened by a close-by bomb or the player is
located on a bomb (in our implementation of the game this can only occur after
it itself has placed it), the player looks for a way to avoid the threat by
moving away from the bomb. If looking for a safe position returns no viable
results then there is nothing to do and the player loses. If not the player will
follow the path returned to him by the `findClosestSafeSpot()' method.

On the other subtree we see the tactics the bot will make use of in order to
achieve his goal in defeating his opponents. The `isEnemyReachable()' function
will return whether the closest opponent to the player is within reach,
meaning if there is no obstacle in the path calculated by the A* algorithm. If
there is at least one obstacle in that path then the bot assumes that there is
still time to pick up power-ups instead and focuses on that. Furthermore the
instant the enemy becomes reachable, the bots top priority becomes attacking
the opponent instead.

\subsubsection{Attacking Tactics}
Attacking the enemy can be achieved in various ways. Initially the tactic was the following: if the player has an opponent within 3 blocks away from him then he would place a bomb in order to attack him. Later on during the evaluation process we thought that we could introduce the concept of the bot already knowing the firepower it has in its disposal. That is how we came up with the final simple approach which was the following: if the bot has a player within reach (with respect to the bots firepower) then it will place a bomb to attack them.

\subsubsection{Moving and Path Finding Tactics}
Pulling up the Map class had a lot of positive impact in making the moving of the players easier. This enabled us to make use of all the functions necessary to implement path finding algorithms. The path finding algorithm we made use of was the A* algorithm. At this point we had to determine the costs of moving through the various types of blocks in the map. We have three types of map cells in the map those are the following :
\begin{itemize}
\item Empty spaces
\item Obstacles
\item Walls
\end{itemize}

Obviously the empty spaces and walls have trivial scores of 1 and undefined (infinity) respectively. However, the one that took some effort in order to figure out, was the obstacle cost.
Initially the players will have obstacles between them and still would require to calculate the distances between them. The final cost we assigned to the `obstacle' class of map cell finally was 4. We observed some weird behaviours when this score was 3. That is the bots would end up trapped by their bombs after placing them. We assumed that the difference between 3 and 4 is that when the cost is fixed to 4 the bot prefer moving around an obstacle more to blasting through it. That is the reason why it will never try to reach a safe position after placing a bomb by blasting its way through another obstacle.

\subsection{Upgrade-First-AI}
\begin{figure}
\centering
\begin{tikzpicture}[node distance =0cm, auto]
\node [decision] {Is current position safe?}
    [decision tree]
    child { node [decision] { Is there a reachable power up? } 
        child { node [outcome] { Go to power up } }
        child { node [decision] { Are more power ups needed? } 
            child { node [outcome] { Blow up nearest reachable block} }
            child { node [decision] { Is an enemy reachable? } 
                child { node [outcome] { Attack enemy } }
                child { node [outcome] { Do nothing } }
            }
        }
    }
    child { node [decision] { Is there a safe position nearby?}
            child { node [outcome] { Go to safe position} }
            child { node [outcome] { Do nothing} }
    };
\end{tikzpicture}
\caption{Decision Tree for the Upgrade-first AI. Power ups are needed in this
decision tree, when the bot has less than 3 bombs, or the bombs have less than 4
squares of fire power.}
\label{fig:treeUpgradeFirst}
\end{figure}
For the Upgrade-First-AI mostly the same code as the Kill-First-AI was used.
This means that the attack mechanism is the same, the path planner is the same,
etc. This means that any difference between the bots is caused by the difference
in their decision trees and not the difference in underlying basic behaviors.

As can be seen in figure \ref{fig:treeUpgradeFirst}, this AI has an extension on the
Kill-First's decision tree. `Power ups needed' means that it aims to get at least 3 bombs and a
firepower of 4 squares in all directions, before trying to kill the opposing
forces. The extra difference this AI has from the other one, is that it searches
the nearest reachable block by only looking at `safe' routes. The ordinary path
planning ignores the threat of bombs in the field, until the bot is about to
step into that square, whereas when looking for reachable blocks to blow up, the
threatened squares are seen as impossible to walk through, forcing the bot to
take as little risk as possible when just looking for a block to blow up. The
ordinary amount of risk is still taken, however, when walking towards power ups,
safe spots or the enemy. 

